# 与求最长子串长度不同，这里打印最长子串
#  需要记录最长子串开始和结束的位置

def longestCommonSubstring(A, B):
	if len(A) == 0 or len(B) == 0: return 0
	tail = 0
	lcs = 0	# 存储最长子串的长度
	for i in range(0,len(A)):
		for j in range(0,len(B)):
			lcs_temp = 0 
			while i+lcs_temp < len(A) and j + lcs_temp < len(B) and A[i+lcs_temp]==B[j+lcs_temp]:
				lcs_temp = lcs_temp+1
			if lcs_temp > lcs:
				tail = j + lcs_temp
				lcs = lcs_temp
	return B[tail-lcs:tail]

# size = longestCommonSubstring('sdfjksail','ksaila')
print(longestCommonSubstring('sdfjksail','ksaila'))

#算法复杂度分析
#双重 for 循环，最坏时间复杂度约为 O(mn * lcs) 